from data_structure import SegmentTreeNode
from utils import util

class Solution:
        # @param root, start, end: The root of segment tree and
        #                          an segment / interval
        # @return: The maximum number in the interval [start, end]
        def query(self, root, start, end):
            walk_packet = {'max':None}
            def walk(pointer, start, end):
                #print 'do walk'
                if pointer == None:
                    return

                _start = pointer.start
                _end = pointer.end
                #print _start,',',_end
                if _start >= start and _end <=  end:
                    #print 'start:',_start,'end:',_end,'max:',pointer.max,'=>',start,':',end
                    if walk_packet['max'] == None:
                        walk_packet['max'] = pointer.max
                    else:
                        walk_packet['max'] = max(walk_packet['max'], pointer.max)
                elif not (_end < start or _start > end):
                        walk(pointer.left, start, end)
                        walk(pointer.right, start, end)
            
            walk(root, start, end)
            return walk_packet['max']
                
def testCase(solution, root, start, end, expect):
    the_max = solution.query(root, start, end)
    print 'query(root, %s, %s), return %s'%(start, end, the_max)
    assert the_max == expect
    return the_max

if __name__=='__main__':
    Builder = __import__('segment-tree-build')
    builder = Builder.Solution()
    solution = Solution()
    root = builder.buildByArray([1, 4, 2 ,3])
    #util.printSegmentTree(root)
    testCase(solution, root, 1, 1, 4)
    testCase(solution, root, 1, 2, 4)
    testCase(solution, root, 2, 3, 3)
    testCase(solution, root, 0, 2, 4)
